{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Partition Array for Maximum Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSumAfterPartitioning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分隔数组以得到最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>arr</code>，请你将该数组分隔为长度 <strong>最多 </strong>为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。</p>\n",
    "\n",
    "<p>返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,15,7,9,2,5,10], k = 3\n",
    "<strong>输出：</strong>84\n",
    "<strong>解释：</strong>数组变为 [15,15,15,9,10,10,10]</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4\n",
    "<strong>输出：</strong>83\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1], k = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 500</code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= arr.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [partition-array-for-maximum-sum](https://leetcode.cn/problems/partition-array-for-maximum-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [partition-array-for-maximum-sum](https://leetcode.cn/problems/partition-array-for-maximum-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,15,7,9,2,5,10]\\n3', '[1,4,1,5,7,3,6,1,9,9,3]\\n4', '[1]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dp(i: int, part_max: int, part_len: int) -> int:\n",
    "            if i == len(arr):\n",
    "                return 0\n",
    "\n",
    "            max_sum_new_part: int = arr[i] + dp(i + 1, arr[i], 1)\n",
    "\n",
    "            max_sum_extend_part: int = 0\n",
    "            if part_len < k:\n",
    "                if arr[i] <= part_max:\n",
    "                    max_sum_extend_part = part_max\n",
    "                else:\n",
    "                    max_sum_extend_part = part_len * (arr[i] - part_max) + arr[i] \n",
    "                max_sum_extend_part += dp(i + 1, max(part_max, arr[i]), part_len + 1)\n",
    "\n",
    "            return max(max_sum_new_part, max_sum_extend_part)\n",
    "\n",
    "\n",
    "        return dp(0, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:\n",
    "        n =len(A)\n",
    "        res = [0 for _ in range(n+1)]\n",
    "        for i in range(len(A)+1):\n",
    "            j = i-1\n",
    "            mx = -float('inf')\n",
    "            while i-j<=K and j>=0:\n",
    "                mx = max(mx,A[j])\n",
    "                res[i] = max(res[i],res[j]+mx*(i-j))\n",
    "                j-=1\n",
    "        return res[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:\n",
    "        '''\n",
    "        思路:动态规划,转移方程dp[i] = max{A[i]+dp[i+1], max(A[i],A[i+1])*2+dp[i+2], max(A[i],A[i+1],A[i+2])*3+dp[i+3], ...}\n",
    "        初始化:dp[N]、dp[N-1]、dp[N-2]、dp[N-K+1]\n",
    "        '''\n",
    "        N = len(A)\n",
    "        dp = [0] * N\n",
    "        for i in range(K):\n",
    "            if N > i:\n",
    "                dp[-i-1] = (i+1) * max(A[-i-1:])\n",
    "        for i in range(N-K-1, -1, -1):\n",
    "            maxtmp = A[i]\n",
    "            for j in range(K):\n",
    "                maxtmp = max(maxtmp, A[i+j])\n",
    "                dp[i] = max(dp[i], (j+1) * maxtmp + dp[i+j+1])\n",
    "        return dp[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:\n",
    "        N = len(A)\n",
    "        dp = [0] * (N + 1)\n",
    "        for i in range(1, N + 1):\n",
    "            max_val = 0\n",
    "            for j in range(i, max(1, i - K + 1) - 1, -1):\n",
    "                max_val = max(max_val, A[j - 1])\n",
    "                dp[i] = max(dp[i], dp[j - 1] + (i - j + 1) * max_val)\n",
    "        return dp[N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:\n",
    "        N = len(A)\n",
    "        dp = [0] * (N + 1)\n",
    "        for i in range(1, N + 1):\n",
    "            max_val = 0\n",
    "            for j in range(i, max(1, i - K + 1) - 1, -1):\n",
    "                max_val = max(max_val, A[j - 1])\n",
    "                dp[i] = max(dp[i], dp[j - 1] + (i - j + 1) * max_val)\n",
    "        return dp[N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n <= k:\n",
    "            return max(arr) * n\n",
    "        dp = [0 for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            tmp = float('-inf')\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if i - j <= k:\n",
    "                    tmp = max(tmp, arr[j])\n",
    "                    dp[i] = max(dp[i], dp[j] + tmp * (i - j))\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, A: List[int], K: int) -> int:\n",
    "        n = len(A)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(1,n+1):\n",
    "            j = i - 1\n",
    "            mx = -float('inf')\n",
    "            while i - j <= K and j >= 0:\n",
    "                mx = max(mx,A[j])\n",
    "                dp[i] = max(dp[i],dp[j]+mx * (i - j))\n",
    "                j -= 1\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        len_arr = len(arr)\n",
    "        if len_arr <= k:\n",
    "            return k * max(arr)\n",
    "        \n",
    "        dp = [0] * (len_arr + 1)\n",
    "\n",
    "        for i in range(1, len_arr + 1):\n",
    "            for j in range(max(i-k, 0), i):\n",
    "                max_num = max(arr[j:i])\n",
    "                dp[i] = max(dp[i], dp[j] + (i - j) * max_num)\n",
    "\n",
    "        return dp[len_arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:    \n",
    "        if not arr:\n",
    "            return []\n",
    "        arr = [0]+arr\n",
    "        n = len(arr)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = arr[0]\n",
    "        for i in range(n):\n",
    "            for j in range(max(0,i-k),i):\n",
    "                max_temp = max(arr[j+1:i+1])\n",
    "                dp[i] = max(dp[j]+max_temp*(i-j),dp[i])\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        meno = dict()\n",
    "        def dfs(index, arr, meno, k):\n",
    "            if index >= len(arr):\n",
    "                return 0\n",
    "            \n",
    "            if index in meno:\n",
    "                return meno[index]\n",
    "            res = 0\n",
    "            max_val = arr[index]\n",
    "            for i in range(k):\n",
    "                new_idx = index + i + 1\n",
    "                if index + i >= len(arr):\n",
    "                    break\n",
    "                max_val = max(max_val, arr[index + i])\n",
    "                res = max(res, dfs(new_idx, arr, meno, k) + (i+1) * max_val)\n",
    "            meno[index] =res\n",
    "            return res\n",
    "\n",
    "        return dfs(0, arr, meno, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, A, K) -> int:\n",
    "        def func(i, K):\n",
    "            if dp[i] != -1:\n",
    "                return dp[i]\n",
    "            max_v, res = -1, -1\n",
    "\n",
    "            if len(A) - i <= K:\n",
    "                return (len(A) - i) * max(A[i:] + [0])\n",
    "\n",
    "            for j in range(i, min(i + K, len(A))):\n",
    "                max_v = max(max_v, A[j])\n",
    "                res = max(res,\n",
    "                          (j - i + 1) * max_v + func(j + 1, K))\n",
    "            dp[i] = res\n",
    "            return res\n",
    "\n",
    "        dp = [-1 for _ in range(len(A))]\n",
    "\n",
    "        return func(0, K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        dp = [-1 for _ in range(len(arr))]\n",
    "        def dfs(idx):\n",
    "            if idx >= len(arr):\n",
    "                return 0\n",
    "            if dp[idx] != -1:\n",
    "                return dp[idx]\n",
    "            interval_max = arr[idx]\n",
    "            ans = 0\n",
    "            for i in range(0, k):\n",
    "                if idx+i >= len(arr):\n",
    "                    break\n",
    "                interval_max = max(interval_max, arr[idx+i])\n",
    "                ans = max(ans, interval_max*(i+1) + dfs(idx+i+1))\n",
    "            dp[idx] = ans\n",
    "            # print(dp[idx])\n",
    "            return ans\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        dp = len(arr) * [0]\n",
    "        for i in range(len(arr)):\n",
    "            max_num = arr[i]\n",
    "            for j in range(i, max(-1, i-k), -1):\n",
    "                max_num = max(max_num, arr[j])\n",
    "                if j == 0:\n",
    "                    dp[i] = max(dp[i], max_num*(i-j+1))\n",
    "                else:\n",
    "                    dp[i] = max(dp[i], dp[j-1]+max_num*(i-j+1))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(pos: int) -> int:\n",
    "        #     ret, mx = 0, 0\n",
    "        #     for i in range(pos + 1, min(n + 1, pos + k + 1)):\n",
    "        #         mx = max(mx, arr[i - 1])\n",
    "        #         ret = max(ret, dfs(i) + mx * (i - pos))\n",
    "        #     return ret\n",
    "\n",
    "        # return max(dfs(i) + max(arr[:i]) * i for i in range(1, k + 1))\n",
    "\n",
    "        f, mx = [0] * (n + 1), 0\n",
    "\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            mx = 0\n",
    "            for j in range(i + 1, min(n + 1, i + k + 1)):\n",
    "                mx = max(mx, arr[j - 1])\n",
    "                f[i] = max(f[i], f[j] + mx * (j - i))\n",
    "        # return max(f[i] + max(arr[:i]) * i for i in range(1, k + 1))\n",
    "\n",
    "        mx, ans = 0, 0\n",
    "        for i in range(1, k + 1):\n",
    "            mx = max(mx, arr[i - 1])\n",
    "            ans = max(ans, f[i] + mx * i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            cur_max = 0\n",
    "            for j in range(1, min(i, k) + 1):\n",
    "                cur_max = max(cur_max, arr[i - j])\n",
    "                dp[i] = max(dp[i], dp[i - j] + cur_max * j)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        d = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            maxValue = arr[i - 1]\n",
    "            for j in range(i - 1, max(-1, i - k - 1), -1):\n",
    "                d[i] = max(d[i], d[j] + maxValue * (i - j))\n",
    "                if j > 0:\n",
    "                    maxValue = max(maxValue, arr[j - 1])\n",
    "        return d[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        self.arr = arr\n",
    "        self.length = arr.__len__()\n",
    "        self.k = k\n",
    "        self.mem = [None for i in range(self.length)]\n",
    "        return self.cal(0)\n",
    "\n",
    "    def cal(self, index: int) -> int:\n",
    "        if index == self.length:\n",
    "            return 0\n",
    "        if self.mem[index] is not None:\n",
    "            return self.mem[index]\n",
    "        else:\n",
    "            res = 0\n",
    "            if (index + self.k) >= self.length:\n",
    "                for i in range(0, self.length-index):\n",
    "                    t = max(self.arr[j] for j in range(index, index+i+1)) * (i+1) + self.cal(index+i+1)\n",
    "                    res = t if t > res else res\n",
    "            else:\n",
    "                for i in range(0, self.k):\n",
    "                    t = max(self.arr[j] for j in range(index, index+i+1)) * (i+1) + self.cal(index+i+1)\n",
    "                    res = t if t > res else res\n",
    "            self.mem[index] = res\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        # 动态规划\n",
    "        def f(arr, i, k, dp):\n",
    "            if i in dp:\n",
    "                return dp[i]\n",
    "            if i == len(arr):\n",
    "                return 0\n",
    "            # 选择 [i, i+k) 位置进行调整\n",
    "            res = arr[i]\n",
    "            ans = 0\n",
    "            for j in range(i, min(i+k, len(arr))):\n",
    "                res = max(res, arr[j])\n",
    "                ans = max(ans, f(arr, j+1, k, dp) + (j-i+1) * res)\n",
    "            dp[i] = ans\n",
    "            return ans\n",
    "        dp = {}\n",
    "        return f(arr, 0, k, dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            cur=arr[i-1]\n",
    "            for j in range(i-1,max(-1,i-k-1),-1):\n",
    "                dp[i]=max(dp[i],dp[j]+cur*(i-j))\n",
    "                if j>0:\n",
    "                    cur=max(cur,arr[j-1])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            max_val = 0\n",
    "            for j in range(1, min(k, i) + 1):\n",
    "                max_val = max(max_val, arr[i - j])\n",
    "                dp[i] = max(dp[i], dp[i - j] + max_val * j)\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        d = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            maxValue = arr[i - 1]\n",
    "            for j in range(i - 1, max(-1, i - k - 1), -1):\n",
    "                d[i] = max(d[i], d[j] + maxValue * (i - j))\n",
    "                if j > 0:\n",
    "                    maxValue = max(maxValue, arr[j - 1])\n",
    "        return d[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        res = [0]*len(arr)\n",
    "        res[0] = arr[0]\n",
    "        for i in range(1, k):\n",
    "            res[i] = max(arr[:i+1]) * (i+1)\n",
    "        print(res)\n",
    "        for i in range(k, len(arr)):\n",
    "            mx = 0\n",
    "            for j in range(i, i-k, -1):\n",
    "                mx = max(mx, arr[j])\n",
    "                res[i] = max(res[i], res[j-1] + mx*(i-j+1))\n",
    "            print(res)\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos: int) -> int:\n",
    "            ret, mx = 0, 0\n",
    "            for i in range(pos + 1, min(n + 1, pos + k + 1)):\n",
    "                mx = max(mx, arr[i - 1])\n",
    "                ret = max(ret, dfs(i) + mx * (i - pos))\n",
    "            return ret\n",
    "\n",
    "        return max(dfs(i) + max(arr[:i]) * i for i in range(1, k + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        dp=[0]*100001\n",
    "        for i in range(n):\n",
    "            cnt=0\n",
    "            maxv=0\n",
    "            dp[i]=0\n",
    "            for j in range(i,-1,-1):\n",
    "                if arr[j]>maxv:\n",
    "                    maxv=arr[j]\n",
    "                cnt+=1\n",
    "                if cnt>k:\n",
    "                    break\n",
    "                if j==0:\n",
    "                    dp[i]=max(dp[i],cnt*maxv)\n",
    "                else:\n",
    "                    dp[i]=max(dp[i],dp[j-1]+cnt*maxv)\n",
    "        return dp[n-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        @cache\n",
    "        def dfs(j):\n",
    "            if j==-1:\n",
    "                return 0\n",
    "            res=-inf\n",
    "            mx=-inf\n",
    "            for i in range(j-1,max(-1,j-k)-1,-1):\n",
    "                mx=max(mx,arr[i+1])\n",
    "                res=max(res,dfs(i)+mx*(j-i))\n",
    "            return res\n",
    "        return dfs(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int) -> int:\n",
    "            # i=-1 时不会进入循环\n",
    "            res = mx = 0\n",
    "            for j in range(i, max(i - k, -1), -1):\n",
    "                mx = max(mx, arr[j])  # 一边枚举 j，一边计算子数组的最大值\n",
    "                res = max(res, dfs(j - 1) + (i - j + 1) * mx)\n",
    "            return res\n",
    "        return dfs(len(arr) - 1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
